UVa/705 - Slash maze/705.cpp

   1 #include <algorithm>
   2 #include <iostream>
   3 #include <map>
   4 #include <vector>
   5 #include <set>
   6
   7 using namespace std;
   8
   9 typedef pair<int, int> node;
  10 typedef map<node, set<node> > graph;
  11
  12 int longest;
  13 int qty;
  14
  15 graph g;
  16
  17 map<node, int> d;
  18
  19 void dfs(const node &u){
  20   set<node> &vecinos = g[u];
  21   for (set<node>::iterator i = vecinos.begin(); i != vecinos.end(); ++i){
  22     if (d.count(*i)){
  23       if (d[*i] + 1 < d[u]){
  24         printf("Cycle from (%d, %d) to (%d, %d)\n", i->first, i->second, u.first, u.second);
  25         qty++;
  26         longest = max(longest, d[u] - d[*i] + 1);
  27       }
  28     }else{
  29       d[*i] = d[u] + 1;
  30       dfs(*i);
  31     }
  32   }
  33 }
  34
  35 int main(){
  36   int w,h;
  37   int mazeNo = 1;
  38   while (cin >> w >> h && w && h){
  39     g.clear();
  40     d.clear();
  41
  42     longest = -1;
  43     qty = 0;
  44
  45     for (int i=0; i<w; ++i){
  46       for (int j=0; j<h; ++j){
  47
  48           g[node(2*i, j)].insert(node(2*i-1, j));
  49           g[node(2*i-1, j)].insert(node(2*i, j));
  50
  51           g[node(2*i+1, j)].insert(node(2*i+2, j));
  52           g[node(2*i+2, j)].insert(node(2*i+1, j));
  53
  54
  55         char c;
  56         cin >> c;
  57         if (c == '\\'){
  58
  59             g[node(2*i, j)].insert(node(2*i, j+1));
  60             g[node(2*i, j+1)].insert(node(2*i, j));
  61
  62
  63             g[node(2*i+1, j)].insert(node(2*i+1, j-1));
  64             g[node(2*i+1, j-1)].insert(node(2*i+1, j));
  65
  66
  67         }else if (c == '/'){
  68             g[node(2*i,j)].insert(node(2*i, j-1));
  69             g[node(2*i,j-1)].insert(node(2*i, j));
  70
  71
  72             g[node(2*i+1,j)].insert(node(2*i+1, j+1));
  73             g[node(2*i+1,j+1)].insert(node(2*i+1, j));
  74
  75
  76         }else{
  77           cerr << "Unrecognized char in input" << endl;
  78         }
  79       }
  80     }
  81
  82     /*for (map<node, set<node> >::iterator i = g.begin(); i != g.end(); ++i){
  83       printf("Vecinos de (%d, %d):\n", i->first.first, i->first.second);
  84       set<node> v = i->second;
  85       for (set<node>::iterator j = v.begin(); j != v.end(); ++j){
  86         printf("(%d, %d) ", j->first, j->second);
  87       }
  88       cout << endl;
  89       }*/
  90
  91     for (map<node, set<node> >::iterator i = g.begin(); i != g.end(); ++i){
  92       if (d.count(i->first) == 0){
  93         d[i->first] = 0;
  94         dfs(i->first);
  95       }
  96     }
  97
  98     printf("Maze #%d:\n", mazeNo++);
  99     if (qty == 0){
 100       printf("There are no cycles.\n");
 101     }else{
 102       printf("%d Cycles; the longest has length %d\n", qty, longest);
 103     }
 104     printf("\n");
 105
 106
 107
 108   }
 109   return 0;
 110 }
 111